#include<bits/stdc++.h>
using namespace std;
const int N=(1<<18),P=998244353,G[2]={3,(P+1)/3};
int rv[N],pw2[N];
int fpw(int a,int x){
	int s=1;
	for(;x;x>>=1,a=1ll*a*a%P) if(x&1) s=1ll*s*a%P;
	return s;
}
void dft(int* a,int n,int p){
	for(int i=0;i<n;i++) if(i<rv[i]) swap(a[i],a[rv[i]]);
	for(int i=1;i<n;i<<=1){
		int wn=fpw(G[p],(P-1)/(i*2));
		for(int j=0;j<n;j+=(i<<1)){
			int w=1;
			for(int k=0;k<i;k++,w=1ll*wn*w%P){
				int x=a[j+k],y=1ll*a[i+j+k]*w%P;
				a[j+k]=(x+y)%P; a[i+j+k]=(x-y+P)%P;
			}
		}
	}
}
int poly_mul(int* A,int* B,int* C,int m){
	//puts("poly_mul");
	//cout<<m<<endl;
	int p=0,n=1;
	while(n<=m) n<<=1,p++;
	//for(int i=0;i<n;i++) cout<<A[i]<<" "<<B[i]<<endl;
	for(int i=0;i<n;i++) rv[i]=(rv[i>>1]>>1)|((i&1)<<(p-1));
	dft(A,n,0); dft(B,n,0);
	for(int i=0;i<n;i++) C[i]=1ll*A[i]*B[i]%P;
	dft(C,n,1); int iv=fpw(n,P-2);
	for(int i=0;i<n;i++) C[i]=1ll*C[i]*iv%P;
	//for(int i=0;i<n;i++) cout<<C[i]<<endl;
	return n;
}
